

//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
// 
// 
// Related Topics 数组 回溯 
// 👍 1243 👎 0




import java.util.*;

/**
 * 51.N 皇后.n-queens
 *
 * @author orz
 * @since 2022-03-28 20:56:09
 **/

class Solution_51 {
    public static void main(String[] args) {
        Solution solution = new Solution_51().new Solution();
        List<List<String>> lists = solution.solveNQueens(8);
        for (int i = 0; i < lists.size(); i++) {
            List<String> item = lists.get(i);
            System.out.println("第"+i+"个解法");
            for (String s : item) {
                System.out.println(s);
            }
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        List<List<String>> solutions = new ArrayList<>();

        public List<List<String>> solveNQueens(int n) {
            //记录每个解法中每行皇后的下标位置
            int[] queens = new int[n];
            //记录已经摆放的皇后所在的列的下标位置
            Set<Integer> columns = new HashSet<>();
            //记录已经摆放的皇后左对角线差
            Set<Integer> leftDiagonals = new HashSet<>();
            //记录已经摆放的皇后的右对角线和
            Set<Integer> rightDiagonals = new HashSet<>();;
            backTrack(queens,n,0,columns,leftDiagonals,rightDiagonals);
            return solutions;
        }

        /**
         *
         * @param queens 记录每个解法中每行皇后的下标位置
         * @param n 棋盘大小
         * @param row 当前行数
         * @param columns 记录已经摆放的皇后所在的列的下标位置
         * @param leftDiagonals 记录已经摆放的皇后左对角线差
         * @param rightDiagonals 记录已经摆放的皇后的右对角线和
         */
        private void backTrack(int[] queens, int n, int row, Set<Integer> columns, Set<Integer> leftDiagonals, Set<Integer> rightDiagonals) {
            if(row == n){
                //到达最后一行，那就要生成当前解法
                generateBoard(queens,n);
                return;
            }

            //对当前行从左到右做循环
            for (int i = 0; i < n; i++) {
                //当前点的左对角线差/右对角线和
                int leftDiagonal = row - i,rightDiagonal = row + i;
                //如果同一列或同一左斜线或同一右斜线上已经有皇后了，就排除当前位置，判断下一位置
                if(columns.contains(i) || leftDiagonals.contains(leftDiagonal)
                        || rightDiagonals.contains(rightDiagonal)){
                    continue;
                }
                //添加当前行的数据，给下一行判断使用
                columns.add(i);
                leftDiagonals.add(leftDiagonal);
                rightDiagonals.add(rightDiagonal);
                //记录当前行皇后所在位置的下标
                queens[row] = i;
                backTrack(queens,n,row+1,columns,leftDiagonals,rightDiagonals);
                //当前解法处理完，清理各个循环存入的记录
                columns.remove(i);
                leftDiagonals.remove(leftDiagonal);
                rightDiagonals.remove(rightDiagonal);
                queens[row] = -1;
            }
        }

        /**
         * 生成当前解法的棋盘
         * @param queens 每行皇后的下标位置
         * @param n 棋盘大小
         */
        private void generateBoard(int[] queens, int n) {
            List<String> solution = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                char[] row = new char[n];
                Arrays.fill(row,'.');
                row[queens[i]] = 'Q';
                solution.add(new String(row));
            }
            solutions.add(solution);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}